from collections import deque

def bidirectional_dfs(maze):
    if not maze or not maze[0]:
        return -1

    rows, cols = len(maze), len(maze[0])
    start = (0, 0)
    end = (rows - 1, cols - 1)

    # 起点和终点的DFS栈
    start_stack = deque([(start, [start])])
    end_stack = deque([(end, [end])])

    # 起点和终点的访问集合
    start_visited = {start: [start]}
    end_visited = {end: [end]}

    # 方向数组
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while start_stack and end_stack:
        # 从起点扩展
        (x, y), path = start_stack.pop()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] == 0:
                if (nx, ny) in end_visited:
                    return path + end_visited[(nx, ny)][::-1]
                if (nx, ny) not in start_visited:
                    start_visited[(nx, ny)] = path + [(nx, ny)]
                    start_stack.append(((nx, ny), path + [(nx, ny)]))

        # 从终点扩展
        (x, y), path = end_stack.pop()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] == 0:
                if (nx, ny) in start_visited:
                    return start_visited[(nx, ny)] + path[::-1]
                if (nx, ny) not in end_visited:
                    end_visited[(nx, ny)] = path + [(nx, ny)]
                    end_stack.append(((nx, ny), path + [(nx, ny)]))

    return -1


# 测试用例
maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
]
print(bidirectional_dfs(maze))  # 输出: [(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4)]